int binary_search(int *a, int num, int t)
{
    int low = -1, high = num - 1;
    while (low + 1 != high) {
        int middle = low + (high - low) / 2;   //防止溢出
        if (a[middle] < t) {
            low = middle;
        } else {
            high = middle;
        }
    }
    //assert：　low +1 = high && a[low] < t && a[high] >= t
    if (a[high] != t) {
        return -1;
    } else {
        return high;
    }
}

void quick_sort(int s[], int l, int r)
{
    if (l < r) {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j) {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if(i < j)
                s[i++] = s[j];

            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}
